package dataStructure.linkedList.binaryTree;

import letcode.util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description: 二叉树的中序遍历
 * @Date: 2020/4/22
 * @Author: 许群星
 */
public class InorderTraversal {
    //顺序： 左，中，右
    ArrayList<Integer> list=new ArrayList<>();

    //递归方法    把取值放到中间即可
    public List<Integer> inorder(TreeNode root){
        //为空则返回
        if (root==null)
            return list;



        if (root.left!=null)
            inorder(root.left);

        list.add(root.val);

        if (root.right!=null)
            inorder(root.right);

        return list;
    }

    //迭代
    public List<Integer> inorder_diedai(TreeNode root){
        LinkedList<TreeNode> stack=new LinkedList<>();
        LinkedList<Integer> res=new LinkedList<>();
        TreeNode curr=root;

        while (curr!=null||!stack.isEmpty()){
            while (curr!=null){
                stack.push(curr);
                curr=curr.left;
            }
            curr=stack.pop();
            res.add(curr.val);
            curr=curr.right;
        }
        return res;
    }
}
